package com.hw.collection;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import com.utility.RandomGenerator;

public class Arrays {

	
	
	public int findMax(int[] A){
		int max=Integer.MIN_VALUE;
		for(int i=0;i<A.length;i++)
			if(A[i]>max)
				max=A[i];
		return max;
	}
	
	public int findMin(int[] A){
		int min=Integer.MAX_VALUE;
		for(int i=0;i<A.length;i++)
			if(A[i]<min)
				min=A[i];
		return min;
	}
	public int median(int[] A,int K){
		
		return median(A,K,findMin(A),findMax(A),(A.length+1)/2-1,A.length);
	}
	
	public int countNumbers(int[] A, int lInc, int rInc){
		int len=A.length;
		int count=0;
		for(int i=0;i<len;i++){
			if(A[i]>=lInc && A[i]<=rInc)
				count++;
		}
		return count;
	}
	
	public int findNum(int[] A, int l, int r,int pos){
		//Extra 3log3 overhead max??
		int len=A.length;
		int i=0;
		List<Integer> ll=new ArrayList<Integer>();
		for(i=0;i<len;i++){
			if(A[i]>=l && A[i]<=r)
				ll.add(A[i]);
		}
		Collections.sort(ll);
		return ll.get(pos);
	}
	public int median(int[] A, int K, int lInc, int rInc,int medianPos,int N){
		if(N<=K){
			if(K<=3)
				return findNum(A,lInc,rInc,medianPos);
			K=K/2;
			return median(A,K,lInc,rInc,medianPos,N);
		}
		int size=rInc-lInc+1;
		int boxSize=size/K;
		int prevCount=0;
		int curCount=0;
		int l=lInc;
		for(int i=0;i<K;i++){
			prevCount=curCount;
			curCount+=countNumbers(A,l,l+boxSize);
			if(curCount>medianPos)
				break;
			l=l+boxSize+1;
			
		}
		return median(A, K, l,l+boxSize ,medianPos-prevCount,curCount-prevCount);
	}
	
	public boolean testMedian(){
		int arraySize=100;
		for(int i=99;i<arraySize;i++){
			int[] A=new int[i];
			for(int j=0;j<i;j++){
				A[j]=RandomGenerator.randInt(-500, 500);
			}
			List<Integer>l=new ArrayList<Integer>();
			for(int p=0;p<i;p++)
				l.add(A[p]);
			Collections.sort(l);
			int medd=l.get((i-1)/2);
			for(int k=2;k<i;k++){
				int med=median(A,k);
				if(med!=medd)
					return false;
			}
		}
		return true;
	}
}
